package com.copa.l338;

import java.util.Arrays;

/**
 * @author copa
 * @createDate 2022-08-06 13:58
 * @function Brian Kernighan 算法
 */
public class Test2 {

    public int[] countBits(int n) {
        int[] result = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            // 由于题目不能用内置函数
            //result[i] = Integer.bitCount(i);
            result[i] = countOne(i);
        }
        return result;
    }

    private int countOne(int i) {
        int sum = 0;
        while (i > 0) {
            i &= (i - 1);
            sum++;
        }
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Test2().countBits(5)));
    }
}
